1194E - Count The Rectangles - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
const int M = 5e3;
const int N = (1 << 14);
int t[2 * N];
void update(int pos, int x) {
    for(t[pos += N] += x; pos > 1; pos >>= 1) {
        t[pos >> 1] = t[pos] + t[pos ^ 1];
    }
}
int get(int l, int r) {
    int res = 0;
    for(l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
        if(l & 1) res += t[l++];
        if(r & 1) res += t[--r];
    }
    return res;
}

struct Xseg {
    int h;
    int l, r;
};
struct Yseg {
    int v;
    int l, r;
};
vector<Xseg> h;
vector<Yseg> v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1 += M;
        x2 += M;
        y1 += M;
        y2 += M;
        if(y1 > y2) swap(y1, y2);
        if(x1 > x2) swap(x1, x2);
        if(x1 == x2) 
            v.push_back({x1, y1, y2});
        else 
            h.push_back({y1, x1, x2});
    }
    sort(v.begin(), v.end(), [](Yseg a, Yseg b){return (a.r < b.r);});
    sort(h.begin(), h.end(), [](Xseg a, Xseg b){if(a.h == b.h) return a.r < b.l; return (a.h < b.h);});
    // for(auto c : h) 
    //     cout << c.h << ' ' << c.l << ' ' << c.r << '\n';
    // cout << '\n';
    // for(auto c : v) 
    //     cout << c.v << ' ' << c.l << ' ' << c.r << '\n';
    // cout << '\n';
    // return 0;
    ll ans = 0;
    for(int i = 0; i < (int)h.size(); i++) {
        Xseg cur = h[i];
        vector<pair<int, int>> t;
        for(int i = 0; i < (int)v.size(); i++) {
            if(v[i].v < cur.l || v[i].v > cur.r || v[i].l > cur.h || v[i].r < cur.h) continue;
            t.push_back({v[i].v, v[i].r}); 
            update(v[i].v, +1);
        }
        int l = 0;
        for(int j = i + 1; j < (int)h.size(); j++) {
            Xseg an = h[j];
            while(l < (int)t.size() && t[l].second < an.h) {
                update(t[l].first, -1);
                l++;
            }
            if(l == (int)t.size()) break;
            int ql = max(cur.l, an.l), qr = min(cur.r, an.r);
            if(ql > qr) continue;
            ll val = get(ql, qr); 
            ans += val * (val - 1) / 2;
        }
        while(l < (int)t.size()) 
            update(t[l++].first, -1);
    }
    cout << ans;
}